package codeRandomThoughts.Test106从中序与后序遍历序列构造二叉树;

import codeRandomThoughts.utils.TreeNode;

import java.util.Arrays;

//二刷 每次建立新的数组时间复杂度太高
public class Solution2 {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        //递归终止条件
        //数组为空说明遍历到了空结点
        if (inorder.length == 0) {
            return null;
        }

        //后序遍历数组的最后一个元素是根节点
        int rootVal = postorder[postorder.length - 1];
        TreeNode root = new TreeNode();
        root.val = rootVal;

        //找根节点在中序遍历数组中的位置
        int rootIndex = 0;
        for (int i = 0; i < inorder.length; i++) {
            if (inorder[i] == rootVal) {
                rootIndex = i;
                break;
            }
        }

        //把原来的中序序列按左右子树进行划分
        int[] inorderLeft = Arrays.copyOfRange(inorder, 0, rootIndex);
        int[] inorderRight = Arrays.copyOfRange(inorder, rootIndex + 1, inorder.length);

        //把原来的后序序列按左右子树进行划分
        int[] postorderLeft = Arrays.copyOfRange(postorder, 0, inorderLeft.length);
        int[] postorderRight = Arrays.copyOfRange(postorder, inorderLeft.length, postorder.length - 1);

        root.left = buildTree(inorderLeft, postorderLeft);
        root.right = buildTree(inorderRight, postorderRight);
        return root;
    }
}
